package com.gofaraway.service.algorithm;

import com.gofaraway.service.facade.dto.GpsPoint;
import org.springframework.util.CollectionUtils;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 *  通过 道格拉斯算法 实现抽稀点位 提升接口效率 减轻服务端处理压力
 *  描述如下【红色部分用于辅助理解 可忽略】：
 *
 *  连接当前矢量曲线首尾点a、b，该直线AB为当前矢量曲线的弦；
 *  计算首尾点a、b间所有坐标点到该弦AB的距离，并获取最大距离d及其的坐标点c；
 *  比较最大距离d与给定的阈值thresholdVal，小于阈值，当前弦AB可作为曲线的近似【首尾间的坐标点将被抽稀】，该段矢量曲线处理完毕。
 *  大于阈值，使用最大距离坐标点c分割当前矢量曲线，分割后的两段矢量曲线分别使用1~3的流程进行处理。
 *  全部处理完毕后，依次连接各个分割点形成的折线，即可以作为整个曲线的近似。
 *
 *  原文链接：https://blog.csdn.net/weixin_39168541/article/details/121949210
 *
 * @author ChenPeng
 * @Date 2024/3/29 10:10
 */
public class DataProcessUtil {

    /**
     * 地球半径
     */
    public static final double EARTH_RADIUS = 6378137;

    /**
     * 默认的点到轨迹线最大距离误差阈值（单位：米）
     */
    private static final double DEFAULT_MAX_REFERENCE = 300;

    /**
     * DP算法入口
     * 传入压缩前的轨迹点集合
     * 输出压缩后的结果轨迹点集合
     *
     * @param originPoints 压缩前的轨迹点集合
     * @return 压缩后的轨迹点
     */
    public static List<GpsPoint> dpCompress(List<GpsPoint> originPoints) {
        if (CollectionUtils.isEmpty(originPoints)) {
            return originPoints;
        }
        return dpCompress(originPoints, DEFAULT_MAX_REFERENCE);
    }

    public static List<GpsPoint> dpCompress(List<GpsPoint> originPoints, Double dMax) {
        List<GpsPoint> resultPoints = new ArrayList<>();

        //获取第一个原始经纬度点坐标并添加到过滤后的数组中
        resultPoints.add(originPoints.get(0));

        //最大距离误差阈值
        if (dMax == null) {
            dMax = DEFAULT_MAX_REFERENCE;
        }
        int start = 0;
        int end = originPoints.size() - 1;
        compression(originPoints, resultPoints, start, end, dMax);

        //获取最后一个原始经纬度点坐标并添加到过滤后的数组中
        resultPoints.add(originPoints.get(end));

        return resultPoints;
    }


    /**
     * 函数功能：根据最大距离限制，采用DP方法递归的对原始轨迹进行采样，得到压缩后的轨迹
     *
     * @param originPoints：原始经纬度坐标点数组
     * @param resultPoints：保持过滤后的点坐标数组
     * @param start：起始下标
     * @param end：终点下标
     * @param dMax：预先指定好的最大距离误差        计算
     */
    private static void compression(List<GpsPoint> originPoints, List<GpsPoint> resultPoints, int start, int end,
                                    double dMax) {
        //递归结束的条件
        if (start >= end) {
            return;
        }

        // 最大距离
        double maxDistance = 0;
        // 最大距离的下标
        int maxPointLocation = 0;

        for (int i = start + 1; i < end; i++) {
            // 计算当前点到对应线段的距离
            double currentDistance = distanceToSegment(originPoints.get(start), originPoints.get(end),
                    originPoints.get(i));

            // 求出最大距离及最大距离对应点的下标
            if (currentDistance > maxDistance) {
                maxDistance = currentDistance;
                maxPointLocation = i;
            }
        }

        // 若当前最大距离大于等于最大距离误差，则根据最大误差划分中心，继续进递归进行压缩
        // 若当前距离小于最大距离误差，则将中间所有的点舍去
        if (maxDistance >= dMax) {
            // 将原来的线段以当前点为中心拆成两段
            // 将第一段加入结果集
            compression(originPoints, resultPoints, start, maxPointLocation, dMax);

            // 将当前点加入结果集
            resultPoints.add(originPoints.get(maxPointLocation));

            // 将第二段加入结果集
            compression(originPoints, resultPoints, maxPointLocation, end, dMax);
        }
    }

    /**
     * 函数功能：使用三角形面积（使用海伦公式求得）相等方法计算点pX到点pA和pB所确定的直线的距离
     *
     * @param pA：起始点
     * @param pB：结束点
     * @param pX：第三个点
     * @return distance：点pX到pA和pB所在直线的距离(米)
     */
    private static double distanceToSegment(GpsPoint pA, GpsPoint pB, GpsPoint pX) {
        // 首末点位置一样取两点间距离
        if (Objects.equals(pA.getLat(), pB.getLat()) && Objects.equals(pA.getLng(), pB.getLng())) {
            return geoDistance(pA, pX);
        }
        double a = Math.abs(geoDistance(pA, pB));
        double b = Math.abs(geoDistance(pA, pX));
        double c = Math.abs(geoDistance(pB, pX));
        double p = (a + b + c) / 2.0;
        double s = Math.sqrt(Math.abs(p * (p - a) * (p - b) * (p - c)));
        return s * 2.0 / a;
    }

    /**
     * 函数功能：根据数学公式求两个经纬度点之间的距离
     *
     * @param pA：起始点
     * @param pB：结束点
     * @return distance：距离(米)
     */
    private static double geoDistance(GpsPoint pA, GpsPoint pB) {
        if (pA == null || pB == null) {
            return 0;
        }
        double radLat1 = radians(pA.getLat());
        double radLat2 = radians(pB.getLat());
        double deltaLng = radians(pB.getLng() - pA.getLng());
        double top1 = Math.cos(radLat2) * Math.sin(deltaLng);
        double top2 = Math.cos(radLat1) * Math.sin(radLat2) - Math.sin(radLat1) * Math.cos(radLat2) * Math.cos(
                deltaLng);
        double top = Math.sqrt(top1 * top1 + top2 * top2);
        double bottom = Math.sin(radLat1) * Math.sin(radLat2) + Math.cos(radLat1) * Math.cos(radLat2) * Math.cos(
                deltaLng);
        double deltaSigma = Math.atan2(top, bottom);
        return deltaSigma * EARTH_RADIUS;
    }

    /**
     * 函数功能：角度转弧度
     *
     * @param d：角度
     * @return 返回的是弧度
     */
    private static double radians(double d) {
        return d * Math.PI / 180.0;
    }

}
